package com.base.graph;

import java.util.*;

/**
 * 207. 课程表
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 *
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 *
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/course-schedule
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *  扩朴排序
 * @author leon
 * @date 2021年12月14日 17:01
 */
public class CanFinish {
    // 邻接表
    List<List<Integer>> edges;
    // 入度数组
    int[] inedg;

    /**
     * 广度优先
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        inedg = new int[numCourses];
        //  初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            edges.add(new LinkedList<>());
        }
        //  [0,1] 表示 从1到0有一条边
        // 初始化邻接表和入度数组
        for (int[] edg : prerequisites) {
            // 向邻接表中加入 1到0 的路径
            edges.get(edg[1]).add(edg[0]);
            // 0 的入度加1
            inedg[edg[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();

        // 初始化队列
        for (int i = 0; i < numCourses; i++) {
            if (inedg[i]==0){
                queue.add(i);
            }
        }
        int count = 0;
        while (!queue.isEmpty()){
            count++;
            int poll = queue.poll();
            for (int e : edges.get(poll)) {
                // 入度减1
                inedg[e]--;
                if(inedg[e] == 0){
                    queue.add(e);
                }
            }
        }

        return count == numCourses;
    }

    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        inedg = new int[numCourses];
        //  初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            edges.add(new LinkedList<>());
        }
        //  [0,1] 表示 从1到0有一条边
        // 初始化邻接表和入度数组
        for (int[] edg : prerequisites) {
            // 向邻接表中加入 1到0 的路径
            edges.get(edg[1]).add(edg[0]);
            // 0 的入度加1
            inedg[edg[0]]++;
        }

        Deque<Integer> stack = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            if(inedg[i] == 0){
                stack.push(i);
            }
        }

        int count = 0;
        while (!stack.isEmpty()){
            count++;
            Integer pop = stack.pop();
            for (int e : edges.get(pop)) {
                inedg[e]--;
                if(inedg[e] == 0){
                    stack.push(e);
                }
            }
        }
        return count == numCourses;
    }
}
